Konplexutasun konputazionalaren teoria

Konplexutasun konputazionalaren teoria^[1] edo konplexutasun informatikoaren teoria teoria konputazionalaren adar bat da, arazo konputazionalak berezko zailtasunaren arabera sailkatzean eta konplexutasun klase horien arteko erlazioan oinarritzen dena^[2].

Arazo bat berez zaila gisa sailkatzen da, bere konponbideak baliabide konputazional kopuru handia eskatzen badu, erabilitako algoritmoa edozein dela ere. Konplexutasun konputazionalaren teoriak baieztapen hori formalizatzen du arazo horiek aztertzeko eta haiek ebazteko behar diren baliabideen kopuruaren kuantifikaziorako eredu konputazional matematikoak sartuz, hala nola denbora eta memoria.

Konplexutasun konputazionalaren teoriaren helburuetako bat ordenagailuan egin daitekeenaren eta egin ezin denaren muga praktikoak zehaztea da. Konplexutasun konputazionalaren teoriarekin lotutako beste alor batzuk algoritmoen analisia eta konputagarritasunaren teoria dira. Algoritmoen analisiaren eta konplexutasun konputazionalaren teoriaren arteko alde nabarmena da lehena algoritmo jakin batek arazo bat ebazteko behar duen baliabide kopurua zehazteaz arduratzen da, eta, bigarrena, berriz, arazo bera ebazteko erabil litezkeen algoritmo posible guztiak aztertzen ditu.

Konplexutasun konputazionalaren teoria baliabide kopuru jakin batekin ebatzi daitezkeen edo ezin diren arazoak sailkatzen saiatzen da. Era berean, baliabide horiei, murrizketak ezartzea da konputagarritasunaren teoriatik bereizten duena, hau da, zer-nolako arazok ebatzi daitezkeen algoritmikoki.

1. ↑ Complejidad Computacional. .
2. ↑ Dean, Walter. (2016). «Computational Complexity Theory» The Stanford Encyclopedia of Philosophy (Metaphysics Research Lab, Stanford University).